In 3.9G and 4 G communication systems, Orthogonal Frequency Division Multiplexing (OFDM) has become a widely applied technology. In the uplink of the next-generation mobile communication system (Long Term Evolution, LTE) defined by 3GPP, User Equipment (UE) adopts Single Carrier Frequency Division Multiple Access (SC-FDMA) technology. It on the one hand inherits the orthogonal property among OFDM subcarriers and on the other hand overcomes the problem of a large PAPR (Peak to Average Power Ratio) of OFDM technology, thus the objective of raising the efficiency of the power amplifier and reducing power consumption of UE is realized. In an LTE system, the preamble sequence in a random access process adopts a Zadoff-Chu (ZC) sequence. ZC sequence is a sequence with the nature of a Constant Amplitude Zero Auto-Correlation (CAZAC) sequence and bears the characteristics in the following two aspects: (1) the sequence has desirable autocorrelation and cross-correlation. Particularly, when the length of the sequence is a prime number, it has ideal autocorrelation and cross-correlation. In this case, when two users access the system by using different ZC sequences, or different cyclic shifts of a same sequence, their mutual interference is very small; (2) both time domain and frequency domain have the property of ZC and PAPR is low, so it is suitable for the use in uplink.
In an LTE system, the time domain ZC root sequences xu(n) with a length of NZC=839 (format 0˜3) and NZC=139 (format 4) are adopted respectively, where subscript u denotes root sequence number:
                    x        u            ⁡              (        n        )              =          exp      ⁢              {                              -            j                    ⁢                                    π              ·              u              ·                              n                ⁡                                  (                                      n                    +                    1                                    )                                                                    N              ZC                                      }              ,          ⁢      0    ≤    n    ≤                  N        ZC            -      1      
The preamble sequence adopted by UE is a specific cyclic shift of the foregoing ZC root sequence, where cyclic shift value τ is given by the network:xuτ(n)=xn((n+τ)mod NZC)
Then, the foregoing preamble sequence is transformed to frequency domain through Discrete Fourier Transform (DFT) at the first NZC point, and is transmitted on the PRACH of a preamble transmission module through a subcarrier mapping module, a CP (cyclic prefix) insertion module and application of power gain factor (βPRACH). The generation process of a random access preamble in the LTE system is shown in FIG. 1.
In the foregoing process, how to calculate DFT through cyclic shift ZC sequence is one of the key technical points of a preamble generation process. As the length of the ZC sequence is a prime number, its DFT can not be realized by conventional FFT method. This is because conventional FFT typically requires the length of the sequence shall be dividable and realizes DFT through series connection of base station-2, base station-3, base station-4 and other modules. If DFT is directly adopted for the calculation, the calculation will be rather complex. The common approach of the trade is to avoid direct calculation of DFT by making use of some properties of the ZC sequence. For example, to DFT Xuτ(k) of cyclic shift ZC sequence xuτ(n), the following formula is tenable (extension is made based on the condition of cyclic shift):Xuτ(k)=DFT[xuτ(n)]=C·xu(τ)·conj[xu((k·Δ+τ)mod NZC)]
Where, C is a complex constant. Its modulo value satisfies |C|=√{square root over (NZC)}; Δ=u−1 mod NZC, i.e., (Δ·u)mod NZC=1, wherein Δε[0, NZC−1] is a non-negative i.e., wherein Δε[0, NZC−1] is a non-negative integer. As preamble transmission performs one fixed phase rotation and does not affect the detection of preamble in base stations, and fixed gain can be reflected in the control of preamble transmitting power, complex constant C is omitted in the following preamble generation process.
Based on the above formula, DFT of the ZC sequence may be considered as the result of conjugate multiplication of a complex number xu(τ) and another ZC sequence xu((k·Δ+τ)mod NZC). Thus complex DFT may be avoided and only the calculation of xu(τ) and ZC sequence xu((k·Δ+τ)mod NZC) are needed, where variables u, k, Δ and τ are all non-negative integers in a range of [0, NZC−1]. Here:
                    ⁢                            x          u                ⁡                  (          τ          )                    =              exp        ⁢                  {                                    -              j                        ⁢                                          π                ·                u                ·                                  τ                  ⁡                                      (                                          τ                      +                      1                                        )                                                                              N                ZC                                              }                                conj      ⁡              [                              x            u                    ⁡                      (                                          (                                                      k                    ·                    Δ                                    +                  τ                                )                            ⁢                                                mod                  ⁢                  N                                ZC                                      )                          ]              =          exp      ⁢              {                  jπ          ·                                    u              ·                              [                                                      (                                                                  k                        ·                        Δ                                            +                      τ                                        )                                    ⁢                                      (                                                                  k                        ·                        Δ                                            +                      τ                      +                      1                                        )                                                  ]                                                    N              ZC                                      }            
However, in order to calculate sequence conj[xu((k·Δ+τ)mod NZC)], phase factor u·[(k·Δ+τ)(k·Δ+τ+1)] is still needed and a large amount of complex multiplication and modular arithmetic are still involved, so this algorithm is still very complex.